『AGC 023C』Painting Machines

Problem

Time limit : 2sec / Memory limit : 256MB

题意简述：

有$n$个方块排成一行，从左到右编号为$1$到$n$。最初所有的方块都是白色的。我们还有$N-1$台涂漆机，编号为$1$至$N-1$。当操作时，第$i$号机器把第$i$和$i+1$号方块染黑。

Snuke将逐个操作这些机器。他操作它们的顺序是$(1,2,…,N-1)$的一个排列$P$,这意味着第$i$个操作的机器是机器$P_i$。

排列$P$的得分被定义为当机器以$P$指定的顺序操作时，在所有方块第一次被涂成黑色之前操作的机器的数量。找出他所有可能排列的得分总和。因为这可能非常大，计算模$10^9+7$。

door♂

Solution

题目可以转化为求 $\displaystyle \sum_{i = 0}^{N - 2} T(i)$

其中$T(i)$表示用了$i$次操作没有全部染黑的方案数

首先我们有$T(0) = (N - 1)!$

然后分类讨论，一个是因为没用$N-1$而没有全部染黑的方案数是$\displaystyle \binom{N - 2}{i}i!$

如果用了$N - 1$，那么方案是$\displaystyle \left (\binom{N - 2}{i - 1} - W(i - 1) \right )i!$

$W(i)$表示用了一个$N - 1$号机器和其他$i$个机器，把所有方格染黑了的方案数

显然序列里会有$1$

把序列差分一下，会发现这个序列不是$1$就是$2$，也就是一堆$1$和一堆$2$的数目固定，一堆$1$和一堆$2$的和是$N - 2$，这是个二元一次方程，然后求出了$1$的个数和$2$的个数，就是个带重复元素的全排列，答案是 $\displaystyle\frac {(\text{num}_1 + \text{num}_2)! }{\text{num}_1 ! \text{num}_2 !}$

由于其他$N - 1 - i$台机器随意排列，最后还要乘上$(N - i - 1)!$

Code:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#define MAXN 1000010
#define MOD 1000000007
using namespace std;
typedef long long ll;
ll fac[MAXN], invfac[MAXN], ans;
int N;
inline ll fpow(const ll& x, ll c)
{
	register ll res = 1, t = x;
	while (c)
	{
		if (c & 1) res = res * t % MOD;
		t = t * t % MOD;
		c >>= 1;
	}
	return res;
}
inline ll C(const int& n, const int& m)
{
	if (n < m) return 0;
	return fac[n] * invfac[m] % MOD * invfac[n - m] % MOD;
}
inline ll W(const int& k)
{
	int x = N - 2 - k;
	int y = k - x;
	if (x < 0 || y < 0) return 0;
	return fac[k] * invfac[y] % MOD * invfac[x] % MOD;
}
int main()
{
	scanf("%d", &N);
	if (N == 2)
	{
		puts("1");
		return 0;
	}
	fac[0] = invfac[0] = 1;
	for (register int i = 1; i <= N; ++i)
		fac[i] = fac[i - 1] * i % MOD;
	invfac[N] = fpow(fac[N], MOD - 2);
	for (register int i = N - 1; i >= 1; --i)
		invfac[i] = invfac[i + 1] * (i + 1) % MOD;
	ans += fac[N - 1];
	for (register int i = 1; i < N - 1; ++i)
		ans += (C(N - 2, i) + C(N - 2, i - 1) + MOD - W(i - 1))* fac[i] % MOD * fac[N - 1 - i] % MOD, ans %= MOD;
	printf("%lld", ans);
	return 0;
}